//从第一个元素开始，该元素可以认为已经被排序；
// 取出下一个元素，在已经排序的元素序列中从后向前扫描；
// 如果该元素（已排序）大于新元素，将该元素移到下一位置；
// 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
// 将新元素插入到该位置后；
// 重复步骤2~5。

// function Insertion(arr) {
//     var len = arr.length;
//     var proIndex;
//     var current;
//     for (var i = 1; i < len; i++) {
//         proIndex = i - 1;
//         current = arr[i];
//         while (proIndex >= 0 && arr[proIndex] > current) {
//             arr[proIndex + 1] = arr[proIndex];
//             proIndex--;
//         }
//         arr[proIndex + 1] = current
//     }
//     return arr
// }



function Insertion(arr) {
    let len = arr.length;
    let pre;
    let curr;
    for (let i = 1; i < len; i++) {
        pre = i - 1;
        curr = arr[i];
        while (pre >= 0 && arr[pre] > curr) {
            arr[pre + 1] = arr[pre];
            pre--;
        }
        arr[pre + 1] = curr;
    }
    return arr;
}




var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37];

console.log(Insertion(arr));

//时间复杂度：最好的情况原本就是有序O(n) 最坏的情况 O（n的平方） 平均O（n的平方）
//空间复杂度：O（1）